package leetcode_801_900;

public class LeeCode_813 {
    public static void main(String[] args) {
        System.out.println(largestSumOfAverages(new int[]{9, 1, 2, 3, 9}, 3));
        System.out.println(largestSumOfAverages(new int[]{1,2}, 2));
        System.out.println(largestSumOfAverages(new int[]{1,2,3,4,5,6,7}, 4));
    }
    private static double largestSumOfAverages(int[] nums, int k) {
        int n = nums.length;
        if (n == 1)
            return nums[0];
        double[][] tab = new double[n][n];
        int[] sums = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                tab[i][j] = ((double) sums[j + 1] - sums[i]) / (j - i + 1);
            }
        }
        double[][] dp = new double[n][k + 1];
        for (int i = 0; i < n; i++) {
            dp[i][1] = tab[0][i];
        }
        for (int i = 1; i < n; i++) {
            for (int j = 2; j <= Math.min(i + 1, k); j++) {
                for (int p = j - 2; p < i; p++) {
                    dp[i][j] = Math.max(dp[i][j], dp[p][j - 1] + tab[p + 1][i]);
                }
            }
        }
        return dp[n - 1][k];
    }
}